package class202205.demo20.demo18;

import java.util.*;

class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val){
        this.val = val;
    }
}

/**
 * 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
 * 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
 * 建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
 */
public class Main {
    public static int i = 0;
    public static TreeNode createTree(String str){
        TreeNode root = null;
        if (str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }

    /**
     * 中序遍历
     * @param root
     */
    public static void inorder(TreeNode root){
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine()){
            String str = scan.nextLine();
            TreeNode root = createTree(str);
            inorder(root);
        }
    }


    /**
     * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     */

    public void levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return;
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != cur){
                queue.offer(cur.right);
            }
        }
    }

    /*public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new LinkedList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != cur) {
                    queue.offer(cur.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }*/

    /**
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * 百度百科中最近公共祖先的定义为：
     * “对于有根树 T 的两个节点 p、q，
     * 最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;

        TreeNode liftT = lowestCommonAncestor(root.left, p, q);
        TreeNode rightT = lowestCommonAncestor(root.right, p, q);

        if (liftT != null && rightT != null) return root;
        if (liftT != null) return liftT;
        if (rightT != null) return rightT;
        return null;
    }

    public boolean getPush (TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if (root == null || node == null) return false;
        stack.push(root);
        if (root == node) return true;
        boolean key = getPush(root.left,node,stack);
        if (key == true) return true;

        key = getPush(root.right,node,stack);
        if (key == true) return true;
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        Stack<TreeNode> stack1 = new Stack<>();
        getPush(root, p, stack1);

        Stack<TreeNode> stack2 = new Stack<>();
        getPush(root, q, stack2);

        int size1 = stack1.size();
        int size2 = stack2.size();

        if (size1 > size2) {
            int size = size1 - size2;
            while (size != 0) {
                stack1.pop();
                size--;
            }
            while (!stack1.isEmpty() && !stack2.isEmpty()) {
                if (stack1.peek() == stack2.peek()) return stack1.peek();
                else stack1.pop();
                stack2.pop();
            }
        } else {
            int size = size2 - size1;
            while (size != 0) {
                stack2.pop();
                size--;
            }
            while (!stack1.isEmpty() && !stack2.isEmpty()) {
                if (stack1.peek() == stack2.peek()) {
                    return stack1.peek();
                } else {
                    stack1.pop();
                    stack2.pop();
                }
            }
        }
        return null;
    }

    /**
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
     * 数据范围：输入二叉树的节点数 0 \le n \le 10000≤n≤1000，二叉树中每个节点的值 0\le val \le 10000≤val≤1000
     * 要求：空间复杂度O(1)O(1)（即在原树上操作），时间复杂度 O(n)O(n)
     * 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
     * 2.返回链表中的第一个节点的指针
     * 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
     * 4.你不用输出双向链表，程序会根据你的返回值自动打印输出
     * @param pRootOfTree
     * @return
     */


    public TreeNode Convert(TreeNode pRootOfTree) {

        if (pRootOfTree == null) return null;

        inorder1(pRootOfTree);
        TreeNode head = pRootOfTree;

        while (head.left!= null){
            head = head.left;
        }
        return head;
    }

    static TreeNode prev = null;

    public static void inorder1(TreeNode pCur){
        if (pCur == null) return;
        inorder1(pCur.left);

        pCur.left = prev;
        if (prev != null){
            prev.right=pCur;
        }
        prev = pCur;

        //System.out.print(pCur.val + " ");


        inorder1(pCur.right);
    }

    /**
     * 给定两个整数数组preorder 和 inorder，其中preorder 是二叉树的先序遍历，
     * inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     * @param preorder
     * @param inorder
     * @return
     */


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) return null;
        return createTreeByPandI(preorder,inorder,0,inorder.length-1);

    }

    private int findIndexOfI(int[] inorder,int inbegin,int inend,int key){
        for (int i = inbegin;i <= inend;i++ ){
            if (inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    public int preIndex = 0;

    public TreeNode createTreeByPandI(int[] preorder, int[] inorder,int inbegin,int inend){
        if (inbegin > inend){
            //如果满足这个  说明没有左树或者右树
            return null;
        }
        TreeNode root = new TreeNode((char) preorder[preIndex]);
        //找到根在中序遍历中的位置
        int rootIndex = findIndexOfI(inorder,inbegin,inend,preorder[preIndex]);
        if (rootIndex == -1) return  null;
        preIndex++;
        //分别创建左子树和右子树
        root.left = createTreeByPandI(preorder,inorder,inbegin,rootIndex-1);
        root.right = createTreeByPandI(preorder,inorder,rootIndex+1,inend);
        return root;
    }

    /**
     * 给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
     * 空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
     * @param root
     * @return
     */
    public String tree2str(TreeNode root) {
        if (root == null) return null;
        StringBuilder sb = new StringBuilder();
        treeToString(root,sb);
        return sb.toString();
    }

    public void treeToString(TreeNode t,StringBuilder sb){
        if (t == null) return;
        sb.append(t.val);

        if (t.left != null) {
            sb.append("(");
            treeToString(t.left,sb);
            sb.append(")");
        }else {
            //t.left == null;
            if (t.right == null){
                return;
            }else {
                sb.append("()");
            }
        }
        if (t.right != null) {
            sb.append("(");
            treeToString(t.right,sb);
            sb.append(")");
        }
    }

    /**
     * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。  Oj解法(非递归写法)
     * @param root
     * @return
     */
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> ret = new ArrayList<>();
        //需要一个栈
        Stack<TreeNode> stack = new Stack<>();
        //记录
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                //放一个打印一个
                //System.out.print(cur.val + " ");
                ret.add(cur.val);
                cur = cur.left;
            }
            //走到这里  cur == null
            //定义弹出
            TreeNode top = stack.pop();
            cur = top.right;  //这里发现  cur 可能为null  也可能不为null   在外部加while循环  栈里有元素也要继续返回再来一次
        }
        return ret;
    }

    /**
     * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。 Oj做法（非递归）
     * @param root
     * @return
     */
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> ret = new ArrayList<>();
        //需要一个栈
        Stack<TreeNode> stack = new Stack<>();
        //记录
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);

                cur = cur.left;
            }
            //走到这里  cur.left == null
            //定义弹出
            TreeNode top = stack.pop();
            //弹出的时候  就是左子树为null  打印
            ret.add(top.val);
            cur = top.right;  //这里发现  cur 可能为null  也可能不为null   在外部加while循环  栈里有元素也要继续返回再来一次
        }
        return ret;
    }

    /**
     * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。 Oj做法（非递归）
     * @param root
     * @return
     */
    public List<Character> postorderTraversal1(TreeNode root) {
        List<Character> ret = new ArrayList<>();
        //需要一个栈
        Stack<TreeNode> stack = new Stack<>();
        //记录
        TreeNode cur = root;
        TreeNode prev = null;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);

                cur = cur.left;
            }
            //走到这里  cur.left == null
            TreeNode top = stack.peek();
            //如果当前节点的右子树 被打印过 或者 遍历过 直接弹出
            if (top.right == null || top.right == prev) {
                stack.pop();
                ret.add(top.val);
                //如果右子树打印过了  可能会陷入死循环  这里定义一个 prev  还得加限定条件top.right == prev
                prev = top;  //记录最近打印的节点

            } else {
                cur = top.right;
            }
        }
        return ret;
    }

}
